#include<stdio.h>
#include"array.h"

void select_sort(int a[], int n) {
	int i, j, k, t;
	for (i = 0; i < n - 1; i++) {
		for (k = i, j = i + 1; j < n; j++) {
			if (a[j] < a[k])
				k = j;
		}
		if (k - i)
			t = a[k], a[k] = a[i], a[i] = t;
	}
}
void bubble_sort_down(int a[], int n) {
	int i, j, t;
	for (i = 0; i < n - 1; i++)
		for (j = 0; j <= n - i - 2; j++)
			if (a[j] > a[j + 1])
				t = a[j], a[j] = a[j + 1], a[j + 1] = t;

}
void bubble_sort_up(int a[], int n) {
	int i, j, t;
	for (i = 0; i < n - 1; i++)
		for (j = n - 2; j >= i; j--)
			if (a[j] > a[j + 1])
				t = a[j], a[j] = a[j + 1], a[j + 1] = t;

}
void insert_sort(int a[], int n) {
	int k, p, j, t;

	for (k = 1; k <= n - 1; k++) {
		/**insert a[k] to sorted array a[0,k-1]*/
		for (p = k - 1; p >= 0; p--)
			if (a[p] <= a[k])
				break;
		p++;
		if (p - k) {
			t = a[k];
			for (j = k; j >= p + 1; j--)
				a[j] = a[j - 1];
			a[p] = t;
		}
	}
}

int main() {
	int a[] = { 1, 5, 3, 7, 0, 4, 2, 8, 6, 9, };
	int n = sizeof(a) / sizeof(a[0]);
	print(a, n);
	// select_sort(a,n);
	// bubble_sort_down(a,n);
	//bubble_sort_up(a,n);
	insert_sort(a, n);
	print(a, n);

	return 0;
}
